/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2024-04-11
 * Time: 13:12
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class Solution {

    public int preIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int ib, int ie) {
        if (ib > ie) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);

        int rootIndex = findRootIndex(inorder, ib, ie, preorder[preIndex]);

        preIndex++;

        root.left = buildTreeChild(preorder, inorder, ib, rootIndex - 1);
        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, ie);

        return root;
    }

    private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key) {
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}

